﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;
// 链地址法的实现
namespace shuaiming_hash_bucket
{
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] = {
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
	template<class K>
	class HashFunc
	{
	public:
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	// 哈希表中支持字符串的操作
	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 131;
				hash += e;
			}
			return hash;
		}
	};
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
	// 由于是迭代器类和哈希桶嵌套调用，故需提前声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;
	// 迭代器类(涉及迭代器的运算操作)
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HashTable<K, T, KeyOfT, Hash> HT;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
		Node* _node;
		const HT* _ht;

		HTIterator(Node* node, const HT* ht)
			:_node(node)
			, _ht(ht)
		{}
		bool operator==(const Self& s) { return _node == s._node; }
		bool operator!=(const Self& s) { return _node != s._node; }
		Ref operator*() { return _node->_data; }
		Ptr operator->() { return &_node->_data; }
		Self& operator++()
		{
			// 当前桶还有数据，则直接访问当前桶
			if (_node->_next)
				_node = _node->_next;
			// 找下一个桶
			else
			{
				Hash hs;
				KeyOfT kt;
				size_t hashi = hs(kt(_node->_data)) % _ht->_tables.size();
				for (size_t i = hashi + 1; i < _ht->_tables.size(); i++)
				{
					_node = _ht->_tables[i];
					if (_node)
						break;
				}
				if (hashi == _ht->_tables.size())
					_node = nullptr;
			}
			return *this;
		}
	};
	// K 为 T 中key的类型
	// T 可能是键值对，也可能是K
	// KeyOfT: 从T中提取key
	// Hash将key转化为整形，因为哈希函数使用除留余数法
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct HTIterator;
		typedef HashNode<T> Node;
	public:
		typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
		typedef HTIterator<K, const T, const T&, const T*, KeyOfT, Hash> ConstIterator;
		HashTable()
			:_n(0)
		{
			_tables.resize(__stl_next_prime(0));
		}
		size_t size() const { return _n; }
		// 哈希桶的销毁
		~HashTable()
		{
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}
		Iterator Begin()
		{
			// 没有数据，则Begin()==End()
			if (_n == 0)
				return End();
			Node* cur = nullptr;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				cur = _tables[i];
				if (cur)
					break;
			}
			return Iterator(cur, this);
		}
		Iterator End() { return Iterator(nullptr, this); }
		ConstIterator Cbegin() const
		{
			// 没有数据，则Begin()==End()
			if (_n == 0)
				return Cend();
			Node* cur = nullptr;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				cur = _tables[i];
				if (cur)
					break;
			}
			return ConstIterator(cur, this);
		}
		ConstIterator Cend() const { return ConstIterator(nullptr, this); }
		// 插入值为data的元素，如果data存在则不插入
		pair<Iterator, bool> Insert(const T& data)
		{
			// 找到就返回该位置，且不插入(false)
			Iterator it = Find(kt(data));
			if (it != End())
				return { it,false };
			size_t hash0 = hs(kt(data)) % _tables.size();
			// 扩容
			if (_n == _tables.size())
			{
				vector<Node*> newHashTable(__stl_next_prime(_tables.size() + 1));
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						size_t newhash0 = hs(kt(cur->_data)) % newHashTable.size();
						Node* next = cur->_next;
						cur->_next = newHashTable[newhash0];
						newHashTable[newhash0] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				newHashTable.swap(_tables);
			}
			// 头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hash0];
			_tables[hash0] = newnode;
			++_n;
			return { Iterator(newnode,this),true };
		}

		// 在哈希桶中查找值为key的元素
		Iterator Find(const K& key)
		{
			size_t hash0 = hs(key) % _tables.size();
			Node* cur = _tables[hash0];
			while (cur)
			{
				if (kt(cur->_data) == key)
					return Iterator(cur, this);
				cur = cur->_next;
			}
			return End();
		}

		// 哈希桶中删除key的元素
		Iterator Erase(const K& key)
		{
			Iterator find = Find(key);
			if (find == End())
				return End();
			size_t hash0 = hs(key) % _tables.size();
			Node* cur = _tables[hash0];
			while (cur)
			{
				if (kt(cur->_data) == key)
				{
					Iterator it(cur, this);
					++it;
					Node* next = cur->_next;
					if (cur == _tables[hash0])
					{
						_tables[hash0] = next;
					}
					else
					{
						_tables[hash0]->_next = next;
					}
					delete cur;
					--_n;
					return it;
				}
				cur = cur->_next;
			}
			return End();
		}
		// 统计桶的数量
		size_t BucketCount()
		{
			size_t count = 0;
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
					++count;
			}
			return count;
		}
		// 统计Key所在桶的结点数量
		size_t BucketSize(const K& key)
		{
			Iterator it = Find(key);
			if (it == End())
				return 0;
			size_t count = 0;
			size_t hash0 = hs(key) % _tables.size();
			Node* cur = _tables[hash0];
			while (cur)
			{
				++count;
				cur = cur->_next;
			}
			return count;
		}
		size_t Size() const { return _n; }
		bool Empty() const { return _n == 0; }
	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;		    // 表中存储数据个数
		KeyOfT kt;
		Hash hs;
	};
}